//
//  Problem47.swift
//  TestProject 47. 全排列 II
//
//  Created by 武侠 on 2020/11/10.
//  Copyright © 2020 zhulong. All rights reserved.
//

import UIKit

/*
 47. 全排列 II
 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

 示例 1：
 输入：nums = [1,1,2]
 输出：
 [[1,1,2],
  [1,2,1],
  [2,1,1]]
 
 示例 2：
 输入：nums = [1,2,3]
 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
  

 提示：

 1 <= nums.length <= 8
 -10 <= nums[i] <= 10
 */
@objcMembers class Problem47: NSObject {
    func solution() {
        // 该实例超时
        print(permuteUnique([1,1,0,0,1,-1,-1,1]))
    }
    
    func permuteUnique(_ nums: [Int]) -> [[Int]] {
        if nums.count == 0 {
            return []
        }
        
        // 存储所有的结果的数据
        var lists:[[Int]] = []
        
        // 存储当前排列的数组
        var path:[Int] = []
        
        // 判断数组中，哪个值存储到了path中
        var used:[Bool] = []
        for _ in nums {
            used.append(false)
        }
        
        // ❗️重点：排序
        combinaNext(nums.sorted(), &path, &lists, &used)
        return lists
    }
    
    func combinaNext(_ candidates:[Int], _ path: inout [Int], _ lists: inout[[Int]], _ used: inout [Bool]) {
        
        // 判断是否存储了所有的数字
        if path.count == candidates.count {
            if lists.contains(path) == false {
                lists.append(path)
            }
            return
        }
        
        // 从0开始：因为过滤掉用，已经加入到path中的位置
        for i in 0..<candidates.count {
            
            // 过滤
            if used[i] == true {
                continue
            }

            // ❗️重点：在这里剪枝
            //  如果和前一位 是相同的数，但是前一位=false，说明之前被用过了
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
                continue;
            }

            
            path.append(candidates[i])
            used[i] = true
            
            combinaNext(candidates, &path, &lists, &used)
            
            // 回溯
            path.removeLast()
            used[i] = false
        }
        
    }
}
